package com.yequan.leetcode.array.countcharacters;

/**
 * @author : Administrator
 * @date : 2020/3/17
 */
public class RecodeCountCharacters {

    public static void main(String[] args) {
        String[] words1 = new String[]{"cat", "bt", "hat", "tree"};
        String chars1 = "atach";
        String[] words2 = new String[]{"hello", "world", "leetcode"};
        String chars2 = "welldonehoneyr";
        RecodeCountCharacters countCharacters = new RecodeCountCharacters();
        int length = countCharacters.countCharacters1(words1, chars1);
        System.out.println(length);

    }

    /**
     * 算法思想:
     * 1.将字母表中出现的次数存放在一个长度为26的数组charArray中
     * 2.将单词表中每一个单词出现的字母的次数存储在长度为26的数组wordCharArray中
     * 3.比较两个数组中字母出现的次数
     * <p>
     * 复杂度:
     * 时间复杂度: O(n)
     * 空间复杂度: O(k)这里是字母表的大小26
     *
     * @param words
     * @param chars
     * @return
     */
    public int countCharacters1(String[] words, String chars) {
        int[] charArray = new int[26];
        int length = 0;
        chars.chars().forEach(c -> ++charArray[c - 'a']);
        a:
        for (String word : words) {
            int[] wordCharArray = charArray.clone();
            for (char c : word.toCharArray()) {
                //判断字母表中的字母是否能够完全覆盖单词表中的单词
                if (--wordCharArray[c - 'a'] < 0) {
                    continue a;
                }
            }
            length += word.length();
        }
        return length;
    }

    public int countCharacters2(String[] words, String chars) {
        int[] charArray = new int[26];
        int length = 0;
        chars.chars().forEach(c -> ++charArray[c - 'a']);

        a:
        for (String word : words) {
            int[] wordCharArray = charArray.clone();
            for (char c : word.toCharArray()) {
                if (--wordCharArray[c - 'a'] < 0) {
                    continue a;
                }
            }
            length += word.length();
        }
        return length;
    }

    public int countCharacters3(String[] words, String chars) {

        int[] charArray = new int[26];
        int length = 0;

        chars.chars().forEach(c -> ++charArray[c - 'a']);

        a:
        for (String word : words) {
            int[] wordCharArray = charArray.clone();
            for (char c : word.toCharArray()) {
                if (--wordCharArray[c - 'a'] < 0) {
                    continue a;
                }
            }
            length += word.length();
        }
        return length;
    }

    public int countCharacters4(String[] words, String chars) {

        int[] charArray = new int[26];
        int length = 0;

        chars.chars().forEach(c -> ++charArray[c - 'a']);

        a:
        for (String word : words) {
            int[] wordCharArray = charArray.clone();
            for (char c : word.toCharArray()) {
                if (--wordCharArray[c - 'a'] < 0) {
                    continue a;
                }
            }
            length += word.length();
        }
        return length;
    }

    public int countCharacters5(String[] words, String chars) {

        int[] charArray = new int[26];
        int length = 0;

        chars.chars().forEach(c -> ++charArray[c - 'a']);

        a:
        for (String word : words) {
            int[] wordCharArray = charArray.clone();
            for (char c : word.toCharArray()) {
                if (--wordCharArray[c - 'a'] < 0) {
                    continue a;
                }
            }
            length += word.length();
        }
        return length;
    }

    public int countCharacters6(String[] words, String chars) {
        int[] charArray = new int[26];
        chars.chars().forEach(c -> ++charArray[c - 'a']);

        int length = 0;
        a:
        for (String word : words) {
            int[] wordCharArray = charArray.clone();
            for (char c : word.toCharArray()) {
                if (--wordCharArray[c - 'a'] < 0) {
                    continue a;
                }
            }
            length += word.length();
        }
        return length;
    }
}
